package rbTree;



/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-05-02
 * Time: 8:38
 */
public class rbTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public Color color;
        public  TreeNode(int val){
            this.val = val;
            color = Color.RED;
        }
    }
    public TreeNode root;
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root==null){
            root = node;
            root.color = Color.BLACK;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur!=null){
            if(cur.val<val){
                parent = cur ;
                cur = cur.right;
            }else if(cur.val == val){
                return false;
            }else{
                parent =cur;
                cur = cur.left;
            }

        }
        if(parent.val>val){
            parent.left = node;
        }else{
             parent.right = node;
        }
        cur = node;
        parent = cur.parent;
        while(parent!=null && parent.color == Color.RED){

                TreeNode grandFather = parent.parent;
                if(parent == grandFather.left){
                    TreeNode uncle  =  grandFather.right;
                    if(uncle!=null && uncle.color == Color.RED){
                        parent.color = Color.BLACK;
                        uncle.color =Color.BLACK;
                        grandFather.color = Color.RED;
                        cur = grandFather;
                        parent = cur.parent;
                    }else{
                        //uncle不存在或为黑
                        if(cur==parent.left){
                            //右旋g;

                            rotateRight(grandFather);
                            parent.color = Color.BLACK;
                            grandFather.color = Color.RED;
                        }else{
                            //左旋p
                            rotateLeft(parent);
                            TreeNode tmp = cur;
                            cur =parent;
                            parent = tmp;
                            rotateRight(grandFather);
                            parent.color = Color.BLACK;
                            grandFather.color = Color.RED;

                        }
                    }
                }else{
                    TreeNode uncle =  grandFather.left;
                        if(uncle!=null && uncle.color == Color.RED){
                            parent.color = Color.BLACK;
                            uncle.color =Color.BLACK;
                            grandFather.color = Color.RED;
                            cur = grandFather;
                            parent = cur.parent;
                        }else{
                            //uncle不存在或为黑
                            if(cur==parent.right){
                                //右旋g;

                                rotateLeft(grandFather);
                                parent.color = Color.BLACK;
                                grandFather.color = Color.RED;
                            }else{
                                //左旋p
                                rotateRight(parent);
                                TreeNode tmp = cur;
                                cur =parent;
                                parent = tmp;
                                rotateLeft(grandFather);
                                parent.color = Color.BLACK;
                                grandFather.color = Color.RED;

                            }
                        }

                }
            }
        root.color = Color.BLACK;
        return true;
    }

    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL  = subR.left;
        subR.left = parent;
        parent.right = subRL;
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        if(subRL!=null){
            subRL.parent = parent;
        }
        if(parent == root){
            root = subR;
            subR.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subR;
                subR.parent = pParent;
            }else{
                pParent.right = subR;
                subR.parent = pParent;
            }
        }



    }

    private void rotateRight(TreeNode parent) {
        TreeNode pParent = parent.parent;
        TreeNode subL = parent.left;
        TreeNode subLR  = subL.right;
        subL.right = parent;
        parent.left = subLR;
        parent.parent = subL;
        if(subLR!=null){
            subLR.parent = parent;
        }
        if(parent==root){
            root = subL;
            subL.parent = null;
        }else{
            if(pParent.left == parent){

            }else{
                pParent.right = subL;
                subL.parent = pParent;
            }
        }




    }
}
